package 代码记录.剑指offer错题本;

import java.math.BigInteger;

/**
 * @author zx
 * @create 2022-05-28 23:39
 */
public class 剪绳子_14 {
    /**
     1.我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来
     2.dp数组记录从0到n长度的绳子剪掉后的最大乘积,dp[i]表示长度为i的绳子剪成m段后的最大乘积,初始化dp[2] = 1
     3.我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
     4.剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)
       如果剪的话长度乘积即为j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])
     5.第一段长度j可以取的区间为[2,i)，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为
       dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
     6.最后返回dp[n]即可
     * @return
     */
    public int cuttingRope(int n) {
        //dp[i]：长度为i的绳子剪成m段后的最大乘积
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3;i < n + 1;i++){
            for(int m = 2;m < i;m++){
                dp[i] = Math.max(dp[i],Math.max(dp[i - m] * m,m * (i - m)));
            }
        }
        return dp[n];
    }

    /**
     * @return 大数据处理
     */
    public int cuttingRope2(int n) {
        BigInteger[] dp = new BigInteger[n + 1];
//        Arrays.fill(dp, BigInteger.valueOf(1));
        dp[2] = BigInteger.valueOf(1);
        for(int i = 3; i < n + 1; i++){
            for(int m = 1; m < i; m++){
                dp[i] = dp[i].max(BigInteger.valueOf(m * (i - m))).max(dp[i - m].multiply(BigInteger.valueOf(m)));
            }
        }
        return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
    }
}
